package me.project.offer;

/**
 * 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。
 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 * <p>
 *
 * @author mbryce
 * @date 2018/7/1
 */
public class Solution10_3th {
    /**
     * 设m为跳法种数，(n=1,m=1) (n=2,m=2) (n=3,m=4) (n=4,m=8) (n=5,m=16)以此类推
     * <p>
     * AC
     *
     * @param n
     * @return
     */
    public int JumpFloorII(int n) {
        return (int) Math.pow(2, n - 1);
    }

    /**
     * ERROR
     * 假设，一级台阶，有f(1)种方法，二级有f(2)种，以此类推，n级有f(n)种方法。
     * 可以看出，f(1)=1;f(2)=2。
     * 那么，假设n级台阶，那么第一步就有两种情况，跳一步，跟跳两步。
     * 情况一：跳一步，那么接下去的就是f(n-1)；
     * 情况二：跳两步，那么接下去的就是f(n-2)。
     * ......
     * 即f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
     * f(n) = 2^(n-1)
     *
     * @param n
     * @return
     */
    public int JumpFloorII2(int n) {
        if (n <= 1)
            return n;
        int[] fib = new int[n + 1];
        int[] ret = new int[n + 1];
        fib[0] = 0;
        fib[1] = ret[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
            ret[i] = fib[i] + ret[i - 1];
        }
        return ret[n];
    }
}
